/*
 * HeapSort.cpp
 *
 *  Created on: 2015年7月5日
 *      Author: Lor
 */

#include "HeapSort.h"

HeapSort::HeapSort() : BaseSort() {
    childInit("HeapSort");
}

HeapSort::HeapSort(vector<int> data) : BaseSort(data) {
    childInit("HeapSort");
}

void HeapSort::sort() {
    sort(1,true);
}

void HeapSort::sort(int method, bool order) {
    sorted_data = raw_data;
    cal_counter = 0;

    switch(method) {
    case 1:
        my_sort(order);
        break;
    case 2:
//        aha_sort(order, 0, sorted_data.size()-1);
        break;
    }
}

inline int parent(int i) {return i>>1;}
inline int left(int i) {return i<<1;}
inline int right(int i) {return (i<<1)+1;}
static int t;
#define swap(a,b) {t=a;a=b;b=t;}

//静态成员函数不需要在实现部分加上static声明
void HeapSort::maxHeapify(int start, int last) {
    int l = left(start);
    int r = right(start);
    int largest;
    if( l<=last && sorted_data[l]>sorted_data[start] ) {
        cal_counter++;
        largest = l;
    }
    else
        largest = start;
    if( r<=last && sorted_data[r]>sorted_data[largest] ) {
        cal_counter++;
        largest = r;
    }
    if(largest!=start) {
        cal_counter++;
        swap(sorted_data[start],sorted_data[largest]);
        cal_counter++;
        maxHeapify(largest,last);
    }
}

//静态成员函数不需要在实现部分加上static声明
void HeapSort::buildMaxHeap() {
    int size = sorted_data.size();
    int i=size/2-1;
    do {
        maxHeapify(i,size-1);
        cal_counter++;
    }
    while(i--); //从中间到头部
}

//堆排序算法中，我们使用的是最大堆，最小堆通常用于构造优先队列（ItA）
void HeapSort::my_sort(bool order) {
    if(order) {
        buildMaxHeap(); //先建立最大堆
        int i;
        //将大的数依次放到尾部
        for(i=sorted_data.size()-1;i>0;--i) //头部 与 从尾部到正数第二个依次交换
        {
            swap(sorted_data[0],sorted_data[i]);
            cal_counter++;
            maxHeapify(0,i-1);
        }
    }
}
